package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zhangjy
 * @description 二叉树的中序遍历
 * @date 2025/3/5 15:27
 */
public class InorderTraversal_94 {

    public static void main(String[] args) {

    }

    /**
     * 栈（dmsxl）；
     * 栈st，在记录访问过的元素和顺序（出栈的顺序则与访问相反）；
     * cur指当前访问的节点;
     * 当访问的节点cur为空时，就该弹出栈顶节点，处理该节点；
     */
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        while (!st.isEmpty() || cur != null) {
            // 一直向左遍历，直到当前节点左孩子为null
            if (cur != null) {
                // 左
                st.push(cur);
                cur = cur.left;
            } else {
                // 当前cur为其父节点的左孩子，栈顶元素为其父节点
                // 中（处理节点，即记录节点值）
                cur = st.pop();
                res.add(cur.val);
                // 右
                cur = cur.right;
            }
        }

        return res;
    }

    /**
     * 栈：个人解法（同官解）；
     * 就按左中右的顺序处理，出栈记录val；
     * 访问和处理节点顺序不同，需要记录遍历过的节点，和正在访问的节点
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root;
        while (!st.isEmpty() || node != null) {
            // 左子树不空就一直入栈（当前节点及其左孩子入栈，直到找到叶子节点）
            while (node != null) {
                // 左
                st.push(node);
                node = node.left;
            }
            // 根（当前栈顶元素的左子树node为空，开始出栈处理栈顶元素）
            node = st.pop();
            res.add(node.val);
            // 右
            node = node.right;
        }
        return res;
    }

    /**
     * 递归
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // 中序遍历，记录节点值val
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        return vals;
    }

    public void inorder(TreeNode root, List<Integer> vals) {
        // 1.返回值、入参；
        // 无返回值；入参：node、vals；
        // 2.递归终止条件：node==null
        if (root == null) return;

        // 3.单层逻辑：按左—>根—>右顺序，记录本层根节点val，遍历本层左—>右
        inorder(root.left, vals);
        vals.add(root.val);
        inorder(root.right, vals);
    }

}
